package cn.chinaflame.pagodas.utils.LightAlgo;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class DijkstraSearch {
    /*
     * 顶点
     */
    private List<Vertex> vertexs;

    /*
     * 边
     */
    private int[][] edges;

    /*
     * 没有访问的顶点
     */
    private Queue<Vertex> unLighted;

    /**
     * @param vertexs
     * @param edges
     */
    public DijkstraSearch(List<Vertex> vertexs, int[][] edges) {
        this.vertexs = vertexs;
        this.edges = edges;
        initUnVisited();
    }

    public static void main(String[] args) {
        String str = "0301140101, 0301140102, 0301140103, 0301140104, 0301140105, 0301140106, 0301140107, 0301140108, 0301140109, 0301140110, 0301140111, 0301140112, 0301140113, 0301140114, 0301140115, 0301140116, 0301140117, 0301140118, 0301140119, 0301140120, 0301140121, 0301140122, 0301140123, 0301140124, 0301140125, 0301140126, 0301140127, 0301140128, 0301140129, 0301140130, 0301140131, 0301140132, 0301140133, 0301140134, 0301140135, 0301140136, 0301140137, 0301140138, 0301140139, 0301140140, 0301140201, 0301140202, 0301140203, 0301140204, 0301140205, 0301140206, 0301140207, 0301140208, 0301140209, 0301140210, 0301140211, 0301140212, 0301140213, 0301140214, 0301140215, 0301140216, 0301140217, 0301140218, 0301140219, 0301140220, 0301140221, 0301140222, 0301140223, 0301140224, 0301140225, 0301140226, 0301140227, 0301140228, 0301140229, 0301140230, 0301140231, 0301140232, 0301140233, 0301140234, 0301140235, 0301140236, 0301140237, 0301140238, 0301140239, 0301140240, 0301140301, 0301140302, 0301140303, 0301140304, 0301140305, 0301140306, 0301140307, 0301140308, 0301140309, 0301140310, 0301140311, 0301140312, 0301140313, 0301140314, 0301140315, 0301140316, 0301140317, 0301140318, 0301140319, 0301140320, 0301140321, 0301140322, 0301140323, 0301140324, 0301140325, 0301140326, 0301140327, 0301140328, 0301140329, 0301140330, 0301140331, 0301140332, 0301140333, 0301140334, 0301140335, 0301140336, 0301140337, 0301140338, 0301140339, 0301140340, 0301140401, 0301140402, 0301140403, 0301140404, 0301140405, 0301140406, 0301140407, 0301140408, 0301140409, 0301140410, 0301140411, 0301140412, 0301140413, 0301140414, 0301140415, 0301140416, 0301140417, 0301140418, 0301140419, 0301140420, 0301140421, 0301140422, 0301140423, 0301140424, 0301140425, 0301140426, 0301140427, 0301140428, 0301140429, 0301140430, 0301140431, 0301140432, 0301140433, 0301140434, 0301140435, 0301140436, 0301140437, 0301140438, 0301140439, 0301140440, 0301140501, 0301140502, 0301140503, 0301140504, 0301140505, 0301140506, 0301140507, 0301140508, 0301140509, 0301140510, 0301140511, 0301140512, 0301140513, 0301140514, 0301140515, 0301140516, 0301140517, 0301140518, 0301140519, 0301140520, 0301140521, 0301140522, 0301140523, 0301140524, 0301140525, 0301140526, 0301140527, 0301140528, 0301140529, 0301140530, 0301140531, 0301140532, 0301140533, 0301140534, 0301140535, 0301140536, 0301140537, 0301140538, 0301140539, 0301140540, 0301140601, 0301140602, 0301140603, 0301140604, 0301140605, 0301140606, 0301140607, 0301140608, 0301140609, 0301140610, 0301140611, 0301140612, 0301140613, 0301140614, 0301140615, 0301140616, 0301140617, 0301140618, 0301140619, 0301140620, 0301140621, 0301140622, 0301140623, 0301140624, 0301140625, 0301140626, 0301140627, 0301140628, 0301140629, 0301140630, 0301140631, 0301140632, 0301140633, 0301140634, 0301140635, 0301140636, 0301140637, 0301140638, 0301140639, 0301140640, 0301140701, 0301140702, 0301140703, 0301140704, 0301140705, 0301140706, 0301140707, 0301140708, 0301140709, 0301140710, 0301140711, 0301140712, 0301140713, 0301140714, 0301140715, 0301140716, 0301140717, 0301140718, 0301140719, 0301140720, 0301140721, 0301140722, 0301140723, 0301140724, 0301140725, 0301140726, 0301140727, 0301140728, 0301140729, 0301140730, 0301140731, 0301140732, 0301140733, 0301140734, 0301140735, 0301140736, 0301140737, 0301140738, 0301140739, 0301140740";
        System.out.println(str.replaceAll(" ", ""));

    }

    /*
     * 初始化未访问顶点集合
     */
    private void initUnVisited() {
        unLighted = new PriorityQueue<Vertex>();
        for (Vertex v : vertexs) {
            unLighted.add(v);
        }
    }

    /*
     * 搜索各顶点最短路径
     */
    public void search() {
        while (!unLighted.isEmpty()) {
            Vertex vertex = unLighted.element();
            //顶点已经计算出最短路径，设置为"已访问"
            vertex.setLighted(true);
            //获取所有"未访问"的邻居
            List<Vertex> neighbors = getNeighbors(vertex);
            //更新邻居的最短路径
            updatesDistance(vertex, neighbors);
            pop();
        }
        System.out.println("search over");
    }

    /*
     * 更新所有邻居的最短路径
     */
    private void updatesDistance(Vertex vertex, List<Vertex> neighbors) {
        for (Vertex neighbor : neighbors) {
            updateDistance(vertex, neighbor);
        }
    }

    /*
     * 更新邻居的最短路径
     */
    private void updateDistance(Vertex vertex, Vertex neighbor) {
        int distance = getDistance(vertex, neighbor) + vertex.getPath();
        if (distance < neighbor.getPath()) {
            neighbor.setPath(distance);
        }
    }

    /*
     * 从未访问顶点集合中删除已找到最短路径的节点
     */
    private void pop() {
        unLighted.poll();
    }

    /*
     * 获取顶点到目标顶点的距离
     */
    private int getDistance(Vertex source, Vertex destination) {
        int sourceIndex = vertexs.indexOf(source);
        int destIndex = vertexs.indexOf(destination);
        return edges[sourceIndex][destIndex];
    }

    /*
     * 获取顶点所有(未访问的)邻居
     */
    private List<Vertex> getNeighbors(Vertex v) {
        List<Vertex> neighbors = new ArrayList<Vertex>();
        int position = vertexs.indexOf(v);
        Vertex neighbor = null;
        int distance;
        for (int i = 0; i < vertexs.size(); i++) {
            if (i == position) {
                //顶点本身，跳过
                continue;
            }
            distance = edges[position][i];    //到所有顶点的距离
            if (distance < Integer.MAX_VALUE) {
                //是邻居(有路径可达)
                neighbor = getVertex(i);
                if (!neighbor.isLighted()) {
                    //如果邻居没有访问过，则加入list;
                    neighbors.add(neighbor);
                }
            }
        }
        return neighbors;
    }

    /*
     * 根据顶点位置获取顶点
     */
    private Vertex getVertex(int index) {
        return vertexs.get(index);
    }

    /*
     * 打印图
     */
    public void printGraph() {
        int verNums = vertexs.size();
        for (int row = 0; row < verNums; row++) {
            for (int col = 0; col < verNums; col++) {
                if (Integer.MAX_VALUE == edges[row][col]) {
                    System.out.print("X");
                    System.out.print(" ");
                    continue;
                }
                System.out.print(edges[row][col]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
}
